def breadthFirstSearchStart(grid, unit, row, column):
    #print(''.join(['row=',str(row),' col=',str(column),'  unit=',str(unit)]))
    costOfStartingSquare=unit.getMotionType().getCostOf(grid.getCell(row,column).getlType())
    if(costOfStartingSquare==None): #Not able to move on the square it is on
        print(''.join(['Unit on a square it should never access [(',str(row),',',str(column),')=',grid.getCell(row,column).getlType(),']']))
        return(set())
    #print(''.join(['costOfStartingSquare is ',str(costOfStartingSquare)]))
    startingMovement=unit.getMovement()
    a = []
    for i in range(grid.getRows()):
        a.append([])
        for j in range(grid.getColumns()):
            a[i].append(-1)
    return(djikstraSingleUnit(grid,a,unit.getMotionType(),startingMovement,row, column, unit.getTeam()))
#    startMovement=unit.getMovement()+costOfStartingSquare
#    return(bredthFirstSearch(grid,unit.getMotionType(),row,column,startMovement,unit.getTeam(),set()))

def djikstraSingleUnit(grid, tmpGrid, motionType, startingMovement, startingRow, startingColumn,team):
    tmpGrid[startingRow][startingColumn]=startingMovement
    numRow=len(tmpGrid)
    numCol=len(tmpGrid[0])
    validSet=set()
    validSet.add((startingRow,startingColumn))
    change=1
    while(change==1):
        change=0
        for row in range(numRow):
            for col in range(numCol):
                if(tmpGrid[row][col]!=0):
                    deltas=[(-1,0),(0,-1),(1,0),(0,1)]
                    for delta in deltas:
                        newRow=row+delta[0]
                        newCol=col+delta[1]
                        if(((0<=newRow) and (newRow<numRow)) and ((0<=newCol) and (newCol<numCol))):
                            if((grid.getCell(newRow,newCol).getUnit()==None) or (grid.getCell(newRow,newCol).getUnit().getTeam()==team)):
                                movementCost=motionType.getCostOf(grid.getCell(newRow,newCol).getlType())
                                if(movementCost!=None):
                                    currentCost=tmpGrid[row][col]-movementCost
                                    if(currentCost>tmpGrid[newRow][newCol]):
                                        tmpGrid[newRow][newCol]=currentCost
                                        change=1
    for row in range(numRow):
        for col in range(numCol):
            if(tmpGrid[row][col]>=0):
                if(grid.getCell(row,col).getUnit()==None):
                    validSet.add((row,col))
    return(validSet)

def djikstraNew(grid, startingLocations):
    numRow=grid.getRows()
    numCol=grid.getColumns()
    tmpGrid = [[-1 for i in range(numCol)] for j in range(numRow)]
    for location in startingLocations:
        tmpGrid[location[0]][location[1]]=location[2]
    change=1
    while(change==1):
        change=0
        for row in range(numRow):
            for col in range(numCol):
                if(tmpGrid[row][col]!=0):
                    deltas=[(-1,0),(0,-1),(1,0),(0,1)]
                    for delta in deltas:
                        newRow=row+delta[0]
                        newCol=col+delta[1]
                        if(((0<=newRow) and (newRow<numRow)) and ((0<=newCol) and (newCol<numCol))):
                            costPerSquare=1
                            currentCost=tmpGrid[row][col]-costPerSquare
                            if(currentCost>tmpGrid[newRow][newCol]):
                                tmpGrid[newRow][newCol]=currentCost
                                change=1
    return(tmpGrid)
    
def djikstraShortestPath(grid, unit, destinations):
    numRow = grid.getRows()
    numCol = grid.getColumns();
    tmpGrid = [[float('inf') for i in range(numCol)] for j in range(numRow)]
    for destination in destinations:
        tmpGrid[destination[0]][destination[1]] = 0
    motionType = unit.getMotionType()
    team = unit.getTeam()
    change=1
    while(change==1):
        change=0
        for row in range(numRow):
            for col in range(numCol):
                if(tmpGrid[row][col]!=float('inf')):
                    deltas=[(-1,0),(0,-1),(1,0),(0,1)]
                    for delta in deltas:
                        newRow=row+delta[0]
                        newCol=col+delta[1]
                        if(((0<=newRow) and (newRow<numRow)) and ((0<=newCol) and (newCol<numCol))):
                            movementCost=motionType.getCostOf(grid.getCell(newRow,newCol).getlType())
                            if(movementCost!=None):
                                currentCost=tmpGrid[row][col]+movementCost
                                #if((grid.getCell(newRow,newCol).getUnit()!=None) and (grid.getCell(newRow,newCol).getUnit().getTeam()!=team)):
                                #    currentCost = currentCost + 5
                                if(currentCost < tmpGrid[newRow][newCol]):
                                    tmpGrid[newRow][newCol] = currentCost
                                    change = 1
    return(tmpGrid)  

def breadthFirstSearch(grid, motionType, row, column, toGo, team ,validSet):
    if((row>grid.getRows()-1) or (column>grid.getColumns()-1) or (row<0) or (column<0)): #Invalid Square
        return(validSet)
    if(grid.getCell(row,column).getUnit()!=None):
        if(grid.getCell(row,column).getUnit().getTeam()!=team):
            return(validSet)
    #print(''.join(['Checking: row=',str(row),' col=',str(column),'  toGo=',str(toGo)]))
    landType=grid.getCell(row,column).getlType()
    movementCost=motionType.getCostOf(landType)
    if(movementCost==None): #Unable to move here
        return(validSet)
    toGo=toGo-movementCost
    if(toGo<0): #No Movement Left
        #print(''.join(['Unable to reach ',str(row),',',str(column)]))
        return(validSet)
    else:
        #print(''.join(['Valid Square: ',str(row),',',str(column)]))
        validSet.add((row,column))
    breadthFirstSearch(grid, motionType, row+1, column, toGo,team,validSet)
    breadthFirstSearch(grid, motionType, row-1, column, toGo,team,validSet)
    breadthFirstSearch(grid, motionType, row, column+1, toGo,team,validSet)
    breadthFirstSearch(grid, motionType, row, column-1, toGo,team,validSet)
    return(validSet)